This invention relates to an adaptive filter, which is a type of digital filter used for echo cancellation and noise cancellation, among other purposes, and to a method of controlling its operation.
A typical prior art adaptive filter is sketched in FIG. 1 of the attached drawings which is intended for the modeling of an unknown dynamic system. Samples of an input signal or data x(t)are sent at predetermined sampling intervals over an input line 1 to an unknown system 2 which is shown to comprise a secondary delay element 3, noise source 4, and adder 5. The output d(t) from this unknown system 2, which is used as a reference signal, is therefore the addition of the output from the delay element 3 and the noise from its source 4.
The input line 1 is also connected to a transversal filter unit 6, known also as a finite impulse response filter, comprising a series of (N-1) delay elements 7-9. Only three delay elements are shown here for illustrative convenience, with the understanding that N=4. Actually, however, N may be as great as, say, 1024. Each of the delay elements 7-9 imparts a unit delay of one sampling interval to the input data samples x(t). Accordingly, N input data samples x(t), x(t-1), x(t-2)and x(t-3) of different sampling times are obtained concurrently on N lines 10-13, respectively, which are connected respectively to the input line 1 and to the outputs of the (N-1) delay elements 7-9. N coefficient multipliers 14-17 multiply the input data samples x(t)-x(t-3) by respective coefficients w.sub.0 -w.sub.3. The resulting outputs from the multipliers 14-17 are all directed into an adder 18 thereby to be added together into an output y(t). This output y(t)is sent to a subtracter or difference detector 20, which produces a difference signal e(t) representative of the difference between the adder output y(t)and the reference signal d(t).
The coefficients w.sub.0 -w.sub.3 must be updated for each sampling interval. To this end the multipliers 14-17 are all connected to a coefficient updater 19, to which there are also connected the tap lines 10-13 of the transversal filter unit 6 and the output of the subtracter 20.
The output y(t)from the adder 18 can be expressed as EQU y(t)=w.sub.o (t)x(t)+w.sub.1 (t)x(t-1)+w.sub.2 (t)x(t-2)+w.sub.3 (t)x(t-3)
or, more generally, in devices having N multipliers, EQU y(t)=w.sub.o (t)x(t)+w.sub.1 (t)x(t-1). . . W.sub.N -1)(t)x(t-N+1) (1)
where (t-N+1) stands for [t-(N-1)]
The output e(t)from the subtracter 20 is given by EQU e(t)=d(t) - y(t) (2)
The coefficients w.sub.0 -w.sub.3 or w.sub.0 -w.sub.N-1 of the transversal filter unit 6 are so controlled as to minimize the .difference signal e(t). In use of the FIG. 1 device for echo cancellation the filter 6 replicates the echo, and the replica y(t)thereby produced is used for canceling out the echo in the output d(t) from the unknown system 2 by the subtracter 20.
A typical algorithm employed for updating the coefficients is that known as normalized least mean square (NLMS) or learning identification method. The NLMS algorithm updates coefficients according to the equation EQU W(t+1)=W(t)+[Ke(t)/.parallel.X(t).parallel..sup.2 ]X(t) 3)
where
W(t+1)=vectors of N updated coefficients
W(t)=vectors of N coefficients w.sub.0 (t), w.sub.1 (t), . . . w.sub.N-1 (t) before being updated; it can be rewritten, using the symbol T standing for the transpose of a matrix, as EQU W(t)=[w.sub.o (t), w.sub.1 (t), w.sub.2 (t), . . . W.sub.N-1 (t)].sup.T
X(t)=vectors of N input samples x(t), w(t-1), . . . x(t-N+1) of different sampling moments, rewritable as
X(t)=[x(t), x(t-1), . . . x(t-N+1)].sup.T
.parallel.X(t).parallel..sup.2 =inner product of X(t)
e(t)=difference signal obtained from subtracter 20, rewritable as EQU e(t)=.epsilon.(t)+n(t)
where n(t) is the noise under observation, and .epsilon.(t)is the noise-free difference signal expressed as .epsilon.(t)=[H-W(t)].sup.T X(t) where H is the coefficient of the unknown system 2
K=parameter known as step gain.
In short the NLMS algorithm as expressed by Expression (3) is such that each updated set of coefficients are obtained by adding the previous set of coefficients to the product of the vectors X(t) of the input samples x(t)-x(t-N+1)and the difference signal e(t) divided by the inner product of the input sample vectors.
The difference signal e(t) becomes closer and closer to an absolute minimum with the repetition of the updating of the coefficients. This convergence depends to a large extent upon the step gain K, which is greater than zero and not more than one. The greater the step gain, the higher will be the speed of convergence, but the greater will be the estimation error .epsilon.(t), and vice versa. The step gain was fixed, not varied with time, in the original NLMS algorithm, so that faster convergence and smaller convergence error represented objectives that were contradictory to each other.
An improvement of the original NLMS algorithm is suggested by the article entitled "An adaptive Echo Canceler with Variable Step Gain Method" by Seiichi Yamamoto et al. in the Volume E65, Number 1 issue of The Transactions of the Institute of Electronics and Communication Engineers of Japan published in January 1982 by the Institute of Electronics and Communication Engineers of Japan. Essentially, the echo canceler of Yamsmoro et al. is a combination of two adaptive filters. FIG. 2 depicts an adaptation of the Yamamoto et al. duplex echo canceler to the modeling of an unknown system. The duplex adaptive filter system shown enclosed in the dashed outline in this figure can be thought of as comprising a first 21 and a second 21' adaptive filter subsystem, even though the complete system is typically fabricated as a single digital signal processor. Each subsystem 21 or 21' comprises the transversal filter unit 6 or 6', respectively the coefficient updater 19 or 19', respectively and the subtracter 20 or 20', respectively which can all be of the same constructions and the same interconnections as their counterparts in the FIG. 1 system.
The only difference between the two subsystems 21 and 21' is the step gain computer 23 included in the second subsystem 21'. Inputting the difference signals e.sub.1 (t)and e.sub.2 (t) from the subtracters 20 and 20' of both subsystems 21 and 21', the step gain computer 23 outputs a step gain that varies with time, for application to the coefficient updater 19' of the second subsystem. In the first subsystem 21, on the other hand, the step gain is fixed at one, so that the coefficients are updated by the original NLMS method. Since the first subsystem 21 is faster in convergence than the second 21', the noise n(t) is estimated from the difference signal e(t) of the first subsystem, and based on this estimation the variable step gain of the second subsystem is controlled.
Let K.sub.2 (t) be the step gain of the second filter subsystem 21'. Then EQU K.sub.2 (t)=[.delta..sub.e2 '.sup.2 (t)- .delta..sub.n '.sup.2 (t)]/.delta..sub.e2 '.sup.2 (t) (4)
where
.delta..sub.e2 '(t)=mean value of the difference signal e.sub.2 (t) from the subtracter 20' of the second subsystem 21'
.delta..sub.n '.sup.2 (t)=mean value of the noise n(t), rewritable as EQU .delta..sub.n '.sup.2 (t)=0.5 .delta..sub.e1 '.sup.2 (t) (5)
where .delta..sub.e1 '.sup.2 (t) is the mean value of the difference signal e.sub.1 (t) of the first filter subsystem 21.
The step gain computer 23 of the FIG. 2 prior art system, computing the step gain according to Expressions (4) and (5), may be configured as diagramed in FIG. 3. At block 31 is computed the mean value .delta..sub.e1 '.sup.2 (t) of the difference signal e.sub.1 (t) from the subtracter 20, FIG. 2, of the first filter subsystem 21. The mean value is then multiplied by 0.5 at block 32 to obtain .delta..sub.n '.sup.2 (t) of Expression (5). Block 33 indicates a smoothing lowpass filter, comprising a delay element 33a for each sample, a parameter .alpha. multiplier 33b, a (1-.alpha.) multiplier 33c, and an adder 33d. The parameter .alpha. is a value between zero and one.
At block 34 is computed the mean value .delta..sub.e2 '.sup.2, in Expression (4), of the difference signal e.sub.2 (t) from the subtracter 20' of the second filter subsystem 21'. A subtracter 35 performs the subtraction for the numerator of Expression (4), and a divider 36 the division of the same equation. The output from the divider 36 is therefore the step gain K.sub.2 (t) as defined by Expression (4). If the difference signals e.sub.1 (t) and e.sub.2 (t) vary with time, so does the step gain, K.sub.2 (t).
FIG. 4 is a detailed illustration of each of the blocks 31 and 34 of the FIG. 3 step gain computer 23. Included is a squaring circuit 41 which squares the difference signal e.sub.1 (t) or e.sub.2 (t). The output of the squaring circuit 41 is connected to a delay line 42 having (L-1) delay elements or memories Z.sup.-1 for providing L differently delayed outputs on taps connected to an adder 43. The output from the adder 43 is multiplied by 1/L by a multiplier 44.
The coefficient updaters 19 and 19' of the FIG. 2 prior art system, which make the computations of Expression (3) according to the NLMS algorithm, can each be of the FIG. 5 configuration. Each such means comprises a step gain K multiplier 50, a divider 51, an adder 52, four squaring circuits 53-56, four multipliers 57-60, four adders 61-64, and four coefficient storage means 65-68. The four updated coefficients w.sub.0 -w.sub.3 can be obtained as the inputs e(t), x(t), x(t-1), x(t-2) and x(t-3) are supplied at predetermined sampling intervals. The two coefficient updaters 19 and 19' differ, however, in that the step gain K multiplier 50 receives the first step gain K.sub.1 which is fixed at one in the first filter subsystem 21, while in the second subsystem 21' the second step gain K.sub.2 (t) is varied with time, as has been set forth with particular reference to FIG. 3.
Let us consider how the FIG. 2 prior art system converges, assuming that the mean noise level is approximately constant. Initially, when the coefficients are set at suitable values, preferably zero, the estimation error is very large, and so is .delta..sub.e2 '.sup.2 (t) in Expression (4). Consequently, the second step gain K.sub.2 (t)is close to one, meaning a high converging speed. The mean value of the estimation errors will grow smaller with the repetition of coefficient updating. As the numerator of the right side of Expression (4) thus become less in value, so will the second step gain K.sub.2 (t). The mean value of the estimation errors .epsilon.(t) will be infinitely close to that of the noise n(t) in the final state of convergence, and the second step gain K.sub.2 (t) will be very close to zero but never go negative because the estimation error increases with a change in noise level.
The foregoing discussion of convergence holds true, however, only when the noise level is more or less constant. Actually, the mean noise value is computed from the difference signal e.sub.1 (t) of the first subsystem 21 in which the step gain K.sub.1 is fixed at one and which has a large initial estimation error. The mean noise level as initially computed from the difference signal of the first subsystem is therefore much greater than the true mean noise level, so that the second step gain K.sub.2 (t) is significantly less than one. Thus the FIG. 2 prior art system was subject to delay in convergence.
Another modification of the NLMS algorithm, also suggesting a variable step gain, is proposed by Kensaku Fujii et al. in the article "Optimum Adjustment of Step Gain in Learning Identification Algorithm" in the Vol. J75-A, No. 6 issue of The Transations of the Institute of Electronics, Information and Communication Engineers published in June 1992 by the Institute of Electronics, Information and Communication Engineers. Fujii et al. suggests to overcome delay in convergence during the initial period by adjustably varying the second step gain K.sub.2 (t). However, this prior art method is based on the assumption that the system noise is only "white", so that it is unapplicable to variable noise systems.